{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "# test_input = {\n",
    "#     1: [1, 5],\n",
    "#     2: [2, 5, 9],\n",
    "#     3: [3, 5],\n",
    "#     4: [1, 4, 5, 6],\n",
    "#     5: [5],\n",
    "#     6: [1, 5, 6],\n",
    "#     7: [3, 5, 7],\n",
    "#     8: [1, 5, 8],\n",
    "#     9: [5, 9],\n",
    "# }\n",
    "\n",
    "test_input = {\n",
    "    1: [1, 2, 3, 7],\n",
    "    2: [2, 3, 7],\n",
    "    3: [3, 7],\n",
    "    4: [4, 5, 7, 8],\n",
    "    5: [5, 7, 8],\n",
    "    6: [6, 7],\n",
    "    7: [7],\n",
    "    8: [7, 8],\n",
    "    9: [7, 8, 9],\n",
    "    10: [7, 6, 10],\n",
    "    11: [7, 6, 11],\n",
    "    12: [7, 3, 12],\n",
    "    13: [7, 3, 2, 13],\n",
    "    14: [7, 8, 14],\n",
    "    15: [7, 6, 10, 15],\n",
    "    16: [7, 3, 12, 16],\n",
    "    17: [7, 3, 12, 17],\n",
    "    18: [7, 6, 11, 18],\n",
    "    19: [7, 6, 11, 19],\n",
    "    20: [7, 6, 11, 20],\n",
    "}\n",
    "\n",
    "# test_input = {\n",
    "#     1: [1, 2, 3, 7],\n",
    "#     2: [2, 3, 7],\n",
    "#     3: [3, 7],\n",
    "#     4: [4, 5, 7, 8],\n",
    "#     5: [5, 7, 8],\n",
    "#     6: [6, 7],\n",
    "#     7: [7],\n",
    "#     8: [7, 8],\n",
    "#     9: [7, 8, 9],\n",
    "# }\n",
    "\n",
    "# test_input = {\n",
    "#     1: [1],\n",
    "#     2: [1, 2],\n",
    "#     3: [1, 3],\n",
    "#     4: [1, 4],\n",
    "#     5: [1, 2, 5],\n",
    "#     6: [1, 3, 6],\n",
    "#     7: [1, 4, 7],\n",
    "# }\n",
    "# test_input = {1: [1], 2: [1, 2], 3: [1, 3], 4: [1, 4], 5: [1, 2, 5], 6: [1, 2, 6], 7: [1, 3, 7], 8: [1, 3, 8], 9: [1, 4, 9], 10: [1, 4, 10]}\n",
    "nodes = [i + 1 for i in range(len(test_input.keys()))]\n",
    "\n",
    "# 7\n",
    "# ├── 3\n",
    "# │   └── 2\n",
    "# │       └── 1\n",
    "# ├── 6\n",
    "# └── 8\n",
    "#     ├── 5\n",
    "#     │   └── 4\n",
    "#     └── 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(test_input.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_possible(matrix, without: list[int]) -> bool:\n",
    "    indices = list(matrix.keys())\n",
    "    if not indices:\n",
    "        return False\n",
    "    if len(indices) == 1:\n",
    "        return True if set(matrix[indices[0]]).difference(set(without)) else False\n",
    "    else:\n",
    "        for depth in matrix[indices[0]]:\n",
    "            if depth not in without:\n",
    "                new_matrix = matrix.copy()\n",
    "                new_matrix.pop(indices[0])\n",
    "                new_without = without.copy()\n",
    "                new_without.append(depth)\n",
    "                if is_possible(new_matrix, new_without):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def induce(depths: dict, chain: list[int]) -> bool:\n",
    "    updated = False\n",
    "\n",
    "    matrix = {}\n",
    "    for node in chain:\n",
    "        matrix[node] = depths[node]\n",
    "    for node in chain:\n",
    "        if len(depths[node]) == 1:\n",
    "            continue\n",
    "        for depth in depths[node]:\n",
    "            new_matrix = matrix.copy()\n",
    "            new_matrix.pop(node)\n",
    "            without = [depth]\n",
    "            if not is_possible(new_matrix, without):\n",
    "                depths[node].remove(depth)\n",
    "                updated = True\n",
    "    \n",
    "    return updated\n",
    "    \n",
    "\n",
    "def update_depths(depths: dict, node: int, constraint: str, value: int) -> bool:\n",
    "    updated = False\n",
    "    if constraint == \"=\":\n",
    "        if depths[node] != [value]:\n",
    "            depths[node] = [value]\n",
    "            updated = True\n",
    "    elif constraint == \"<=\":\n",
    "        for depth in depths[node].copy():\n",
    "            if depth > value:\n",
    "                depths[node].remove(depth)\n",
    "                updated = True\n",
    "    elif constraint == \">\":\n",
    "        for depth in depths[node].copy():\n",
    "            if depth <= value:\n",
    "                depths[node].remove(depth)\n",
    "                updated = True\n",
    "    return updated"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def update(chains, nodes, depths, parents):\n",
    "    while True:\n",
    "        updated = False\n",
    "        # 探索单链\n",
    "        for k in chains.keys():\n",
    "            # 末节点的深度确定了\n",
    "            if update_depths(depths, k, \"=\", len(chains[k])):\n",
    "                updated = True\n",
    "            # 缩小其余节点的取值范围\n",
    "            max_depth = depths[k][0] - 1\n",
    "            for node in chains[k]:\n",
    "                if node != k and update_depths(depths, node, \"<=\", max_depth):\n",
    "                    updated = True\n",
    "            # 进一步推理\n",
    "            if induce(depths, chains[k]):\n",
    "                updated = True\n",
    "            # 若该链已经全部明了，则添加父子关系\n",
    "            if len(chains[k]) == sum([len(depths[i]) for i in chains[k]]):\n",
    "                parent = None\n",
    "                son = None\n",
    "                for i in range(len(chains[k])):\n",
    "                    for node in chains[k]:\n",
    "                        if depths[node][0] == i + 1:\n",
    "                            son = node\n",
    "                            parents[son] = parent\n",
    "                            parent = son\n",
    "                \n",
    "        # 探索一对链\n",
    "        ks = list(chains.keys())\n",
    "        for i1, k1 in enumerate(ks[:-1]):\n",
    "            for k2 in ks[i1+1:]:\n",
    "                # 找交集，交集中的节点深度<=交集长度，交集外的节点深度>交集长度\n",
    "                intersect = set(chains[k1]).intersection(set(chains[k2]))\n",
    "                union = set(chains[k1]).union(set(chains[k1]))\n",
    "                length = len(intersect)\n",
    "                for node in intersect:\n",
    "                    if update_depths(depths, node, \"<=\", length):\n",
    "                        updated = True\n",
    "                for node in union.difference(intersect):\n",
    "                    if update_depths(depths, node, \">\", length):\n",
    "                        updated = True\n",
    "        if not updated:\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "org: 20---now: 14.095---improve ratio: 0.29525\n"
     ]
    }
   ],
   "source": [
    "times = 0\n",
    "for _ in range(1000):\n",
    "    known_chains = {}\n",
    "    known_nodes = set()\n",
    "    depths = {i: [d + 1 for d in range(len(nodes))] for i in nodes}\n",
    "    parents = {i: None for i in nodes}\n",
    "    for _ in range(len(nodes)):\n",
    "        times += 1\n",
    "        # # way 1: 纯推理，无探索策略（废弃）\n",
    "        # nodes_to_select = list(set(nodes).difference(set(known_chains.keys())))\n",
    "        # selected_node = nodes_to_select[random.randint(0, len(nodes_to_select)-1)]\n",
    "        # way 2: 推理+不探索已知节点\n",
    "        nodes_to_select = list(set(nodes).difference(set(known_chains.keys()).union(set(known_nodes))))\n",
    "        selected_node = nodes_to_select[random.randint(0, len(nodes_to_select)-1)]\n",
    "        # # way 3: 推理+不探索已知节点+选择尽可能未知的节点探索\n",
    "        # nodes_to_select = list(set(nodes).difference(set(known_chains.keys()).union(set(known_nodes))))\n",
    "        # selected_node = nodes_to_select[random.randint(0, len(nodes_to_select)-1)]\n",
    "        # for node in nodes_to_select:\n",
    "        #     if len(depths[node]) > len(depths[selected_node]):\n",
    "        #         selected_node = node\n",
    "\n",
    "        known_chains[selected_node] = test_input[selected_node]\n",
    "        update(known_chains, nodes, depths, parents)\n",
    "        for node in nodes:\n",
    "            if len(depths[node]) == 1:\n",
    "                known_nodes.add(node)\n",
    "        if len(nodes) - 1 == len([i for i in parents.keys() if parents[i] is not None]):\n",
    "            break\n",
    "\n",
    "print(f\"org: {len(nodes)}---now: {times/1000}---improve ratio: {1-times/1000/len(nodes)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "├── 3\n",
      "│   ├── 2\n",
      "│   │   ├── 1\n",
      "│   │   └── 13\n",
      "│   └── 12\n",
      "│       ├── 16\n",
      "│       └── 17\n",
      "├── 6\n",
      "│   ├── 10\n",
      "│   │   └── 15\n",
      "│   └── 11\n",
      "│       ├── 18\n",
      "│       ├── 19\n",
      "│       └── 20\n",
      "└── 8\n",
      "    ├── 5\n",
      "    │   └── 4\n",
      "    ├── 9\n",
      "    └── 14\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# 如果树全部已知，则打印\n",
    "if len(nodes) - 1 == len([i for i in parents.keys() if parents[i] is not None]):\n",
    "    from treelib import Node, Tree\n",
    "\n",
    "    tree = Tree()\n",
    "\n",
    "    for depth in range(max(v[0] for v in depths.values())):\n",
    "        for node in nodes:\n",
    "            if depths[node][0] == depth + 1:\n",
    "                tree.create_node(node, node, parents[node])\n",
    "            \n",
    "    print(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1713265781.5315084"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "time.time()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
